{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Path with Maximum Gold"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getMaximumGold"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #黄金矿工"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为&nbsp;<code>m * n</code> 的网格 <code>grid</code> 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 <code>0</code>。</p>\n",
    "\n",
    "<p>为了使收益最大化，矿工需要按以下规则来开采黄金：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每当矿工进入一个单元，就会收集该单元格中的所有黄金。</li>\n",
    "\t<li>矿工每次可以从当前位置向上下左右四个方向走。</li>\n",
    "\t<li>每个单元格只能被开采（进入）一次。</li>\n",
    "\t<li><strong>不得开采</strong>（进入）黄金数目为 <code>0</code> 的单元格。</li>\n",
    "\t<li>矿工可以从网格中 <strong>任意一个</strong> 有黄金的单元格出发或者是停止。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[0,6,0],[5,8,7],[0,9,0]]\n",
    "<strong>输出：</strong>24\n",
    "<strong>解释：</strong>\n",
    "[[0,6,0],\n",
    " [5,8,7],\n",
    " [0,9,0]]\n",
    "一种收集最多黄金的路线是：9 -&gt; 8 -&gt; 7。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]\n",
    "<strong>输出：</strong>28\n",
    "<strong>解释：</strong>\n",
    "[[1,0,7],\n",
    " [2,0,6],\n",
    " [3,4,5],\n",
    " [0,3,0],\n",
    " [9,0,20]]\n",
    "一种收集最多黄金的路线是：1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; 6 -&gt; 7。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= grid.length,&nbsp;grid[i].length &lt;= 15</code></li>\n",
    "\t<li><code>0 &lt;= grid[i][j] &lt;= 100</code></li>\n",
    "\t<li>最多 <strong>25 </strong>个单元格中有黄金。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [path-with-maximum-gold](https://leetcode.cn/problems/path-with-maximum-gold/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [path-with-maximum-gold](https://leetcode.cn/problems/path-with-maximum-gold/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,6,0],[5,8,7],[0,9,0]]', '[[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        self.grid = grid\n",
    "        self.visited = [[False for _ in grid[0]] for __ in grid]\n",
    "        self.res = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                self.visited[i][j] = True\n",
    "                self.dfs(i, j, 0)\n",
    "                self.visited[i][j] = False\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, x_idx, y_idx, cur_gold):\n",
    "        cur_gold += self.grid[x_idx][y_idx]\n",
    "        self.res = max(self.res, cur_gold)\n",
    "        for direct in ((-1, 0), (1, 0), (0, -1), (0, 1)):\n",
    "            x_idx_n = x_idx + direct[0]\n",
    "            y_idx_n = y_idx + direct[1]\n",
    "            if x_idx_n < 0 or x_idx_n >= len(self.grid) or y_idx_n < 0 or y_idx_n >= len(self.grid[0]) or self.grid[x_idx_n][y_idx_n] == 0 or self.visited[x_idx_n][y_idx_n]:\n",
    "                continue\n",
    "            self.visited[x_idx_n][y_idx_n] = True\n",
    "            self.dfs(x_idx_n, y_idx_n, cur_gold)\n",
    "            self.visited[x_idx_n][y_idx_n] = False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0 \n",
    "        \n",
    "        def dfs(x, y):\n",
    "            if x < 0 or y < 0 or x == m or y == n or not grid[x][y]:\n",
    "                return 0\n",
    "            record = grid[x][y]\n",
    "            grid[x][y] = mx = 0\n",
    "            for dx, dy in (0, 1), (1, 0), (0, -1), (-1, 0):\n",
    "                mx = max(mx, dfs(x + dx, y + dy))\n",
    "            grid[x][y] = record\n",
    "            return record + mx\n",
    "                \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans, dfs(i, j))\n",
    "        \n",
    "        return ans\n",
    "       \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "\n",
    "        def backtrack(i, j, s):\n",
    "            s += grid[i][j]\n",
    "            nonlocal ans\n",
    "            ans = max(s, ans)\n",
    "            tem = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "\n",
    "            for mx, my in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:\n",
    "                if 0 <= mx < m and 0 <= my < n and grid[mx][my] > 0:\n",
    "                    backtrack(mx, my, s)\n",
    "            grid[i][j] = tem\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    backtrack(i, j, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        #copy\n",
    "        m,n =len(grid),len(grid[0])\n",
    "        ans = 0\n",
    "        \n",
    "        def dfs(x,y):\n",
    "            if x <0 or y<0 or x==m or y ==n or not grid[x][y]:\n",
    "                return 0\n",
    "            record = grid[x][y]\n",
    "            grid[x][y]=mx =0\n",
    "            for dx,dy in (0,1),(1,0),(0,-1),(-1,0):\n",
    "                mx = max(mx,dfs(x+dx,y+dy))\n",
    "            grid[x][y] = record\n",
    "            return record+mx\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans,dfs(i,j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(x: int, y: int, gold: int) -> None:\n",
    "            gold += grid[x][y]\n",
    "            nonlocal ans\n",
    "            ans = max(ans, gold)\n",
    "\n",
    "            rec = grid[x][y]\n",
    "            grid[x][y] = 0\n",
    "\n",
    "            for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:\n",
    "                    dfs(nx, ny, gold)\n",
    "\n",
    "            grid[x][y] = rec\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    dfs(i, j, 0)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \n",
    "# O()\t\tO()\n",
    "# 最好击败\t%\t\t%\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid) -> int:\n",
    "        def dfs(i, j, total):\n",
    "            t = grid[i][j]\n",
    "            now = total + t\n",
    "            grid[i][j] = 0  # 标记已走\t越界标记法\n",
    "            # if i - 1 >= 0 and grid[i - 1][j] != 0:  # 向上搜索\n",
    "            #     dfs(i - 1, j, now)\n",
    "            # if i + 1 < m and grid[i + 1][j] != 0:  # 向下搜索\n",
    "            #     dfs(i + 1, j, now)\n",
    "            # if j - 1 >= 0 and grid[i][j - 1] != 0:  # 向左搜索\n",
    "            #     dfs(i, j - 1, now)\n",
    "            # if j + 1 < n and grid[i][j + 1] != 0:  # 向右搜索\n",
    "            #     dfs(i, j + 1, now)\n",
    "            for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:\n",
    "                if 0<=x<m and 0<=y<n and grid[x][y] != 0:\n",
    "                    dfs(x,y,now)\n",
    "\n",
    "            if now > ans[0]:\n",
    "                ans[0] = now\n",
    "            grid[i][j] = t  # 标记回溯\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    dfs(i, j, 0)  # 对每个起点进行深度搜索\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        row,col = len(grid),len(grid[0])\n",
    "        starts = []\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j]!=0:\n",
    "                    starts.append([i,j])\n",
    "        ans = 0\n",
    "        def bks(i,j):\n",
    "            if i<0 or j<0 or i>=row or j>=col or grid[i][j]==0: return 0\n",
    "            temp = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "            down = bks(i+1,j)+(grid[i+1][j] if i+1<row else 0)\n",
    "            up = bks(i,j-1)+(grid[i][j-1] if j-1>=0 else 0)\n",
    "            right = bks(i,j+1)+(grid[i][j+1] if j+1<col else 0)\n",
    "            left = bks(i-1,j)+(grid[i-1][j] if i-1>=0 else 0)\n",
    "            res = max(down,up,right,left)\n",
    "            grid[i][j]=temp\n",
    "            return res\n",
    "        for i,j in starts:\n",
    "            ans=max(ans,bks(i,j)+grid[i][j])\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(i, j, pathsum):\n",
    "            nonlocal res\n",
    "            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]):\n",
    "                return\n",
    "            if onpath[i][j]:\n",
    "                return\n",
    "            if grid[i][j] == 0:\n",
    "                return\n",
    "            directions = [[0,1], [1,0], [-1,0], [0,-1]]\n",
    "            onpath[i][j] = True\n",
    "            pathsum += grid[i][j]\n",
    "            res = max(pathsum, res)\n",
    "\n",
    "            for x, y in directions:\n",
    "                dfs(i+x, j+y, pathsum)\n",
    "            \n",
    "            onpath[i][j] = False\n",
    "            pathsum -= grid[i][j]\n",
    "        \n",
    "        res = 0\n",
    "        onpath = [[False] * len(grid[0]) for _ in range(len(grid))]\n",
    "\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                dfs(i, j, 0)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        def dfs(x, y):\n",
    "            if x < 0 or y < 0 or x == m or y == n or not grid[x][y]:\n",
    "                return 0\n",
    "            record = grid[x][y]\n",
    "            grid[x][y] = 0\n",
    "            mx = 0\n",
    "            for dx, dy in (0, 1), (1, 0), (0, -1), (-1, 0):\n",
    "                mx = max(mx, dfs(x + dx, y + dy))\n",
    "            grid[x][y] = record\n",
    "            return record + mx\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, dfs(i,j))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        maxx=0\n",
    "        def f(i,j,summ=0):\n",
    "            if -1< i < len(grid) and -1< j < len(grid[0]) and grid[i][j]!=0:\n",
    "                summ+=grid[i][j]\n",
    "                temp=grid[i][j]\n",
    "                grid[i][j]=0\n",
    "                f(i+1,j,summ)\n",
    "                f(i-1,j,summ)\n",
    "                f(i,j+1,summ)\n",
    "                f(i,j-1,summ)\n",
    "                grid[i][j]=temp #bianhuiqushengzao\n",
    "            else:\n",
    "                nonlocal maxx\n",
    "                maxx = max(summ,maxx)\n",
    "                return \n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] != 0:\n",
    "                    f(i,j)\n",
    "        return maxx\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        ans=0\n",
    "        directions = [(1,0),(0,1),(-1,0),(0,-1)]\n",
    "        def backtracking(i,j,gold):\n",
    "            nonlocal ans\n",
    "            ans = max(ans,gold)\n",
    "            vis.add((i,j))\n",
    "            for di,dj in directions:\n",
    "                i_,j_ = i+di,j+dj\n",
    "                if 0<=i_<m and 0<=j_<n and (i_,j_) not in vis and grid[i_][j_]!=0:\n",
    "                    backtracking(i_,j_,gold+grid[i_][j_])\n",
    "            vis.remove((i,j))\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]!=0:\n",
    "                    vis = set()\n",
    "                    backtracking(i,j,grid[i][j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        mat = [[False] * n for _ in range(m)]\n",
    "\n",
    "        max_profit = 0 #-float('inf')\n",
    "\n",
    "        def dfs(i, j, path_profit):\n",
    "            nonlocal max_profit\n",
    "            if 0 <= i < m and 0 <= j < n and grid[i][j] > 0 and not mat[i][j]:\n",
    "                pass\n",
    "            else:\n",
    "                return \n",
    "            max_profit = max(max_profit, path_profit + grid[i][j])\n",
    "            #print(\"in\", i, j, max_profit)\n",
    "\n",
    "            mat[i][j] = True\n",
    "            for tmp_i, tmp_j in [[i, j + 1], [i, j - 1], [i + 1, j], [i - 1, j]]:\n",
    "                dfs(tmp_i, tmp_j, path_profit + grid[i][j])\n",
    "            mat[i][j] = False\n",
    "            \n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0:\n",
    "\n",
    "                    dfs(i, j, 0)\n",
    "\n",
    "\n",
    "\n",
    "        return max_profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        dir = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        def dfs(pos, mine, cur):\n",
    "            nonlocal res, grid\n",
    "            res = max(res, cur)\n",
    "            for i in dir:\n",
    "                newx = pos[0] + i[0]\n",
    "                newy = pos[1] + i[1]\n",
    "                if 0 <= newx < len(grid) and 0 <= newy < len(grid[0]) and grid[newx][newy]:\n",
    "                    temp = grid[newx][newy]\n",
    "                    grid[newx][newy] = 0\n",
    "                    dfs((newx, newy), grid, cur + temp)\n",
    "                    grid[newx][newy] = temp\n",
    "\n",
    "        for index, i in enumerate(grid):\n",
    "            for indexj, j in enumerate(i):\n",
    "                if grid[index][indexj]:\n",
    "                    grid[index][indexj] = 0\n",
    "                    dfs((index, indexj), grid, j)\n",
    "                    grid[index][indexj] = j\n",
    "        # dfs(grid)\n",
    "\n",
    "        return(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "\n",
    "        def backtrack(i, j, s):\n",
    "            s += grid[i][j]\n",
    "            nonlocal ans\n",
    "            ans = max(s, ans)\n",
    "            tem = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "\n",
    "            for mx, my in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:\n",
    "                if 0 <= mx < m and 0 <= my < n and grid[mx][my] > 0:\n",
    "                    backtrack(mx, my, s)\n",
    "            grid[i][j] = tem\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    backtrack(i, j, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        self.res = 0\n",
    "        self.grid = grid\n",
    "        self.gold = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if self.grid[i][j] != 0:\n",
    "                    self.dfs(i, j, 0)\n",
    "        return self.res\n",
    "    def dfs(self, x: int, y: int, gold: int) -> None:\n",
    "        m, n = len(self.grid), len(self.grid[0])\n",
    "        gold += self.grid[x][y]\n",
    "        self.res = max(self.res, gold)\n",
    "        temp = self.grid[x][y]\n",
    "        self.grid[x][y] = 0\n",
    "        for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):\n",
    "                if 0 <= nx < m and 0 <= ny < n and self.grid[nx][ny] > 0:\n",
    "                    self.dfs(nx, ny, gold)\n",
    "        self.grid[x][y] = temp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    res = 0\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def go(x, y):\n",
    "            if x < 0 or x >= m:\n",
    "                return 0\n",
    "            if y < 0 or y >= n:\n",
    "                return 0\n",
    "            if grid[x][y] == 0:\n",
    "                return 0\n",
    "            cur = grid[x][y]\n",
    "            grid[x][y] = 0\n",
    "            res = 0\n",
    "            res = max(res, cur + go(x + 1, y))\n",
    "            res = max(res, cur + go(x - 1, y))\n",
    "            res = max(res, cur + go(x, y + 1))\n",
    "            res = max(res, cur + go(x, y - 1))\n",
    "            grid[x][y] = cur\n",
    "            return res\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                self.res = max(go(i,j), self.res)\n",
    "        return self.res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        dir = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        def dfs(pos, mine, cur):\n",
    "            nonlocal res, grid\n",
    "            res = max(res, cur)\n",
    "            for i in dir:\n",
    "                newx = pos[0] + i[0]\n",
    "                newy = pos[1] + i[1]\n",
    "                if 0 <= newx < len(grid) and 0 <= newy < len(grid[0]) and grid[newx][newy]:\n",
    "                    temp = grid[newx][newy]\n",
    "                    grid[newx][newy] = 0\n",
    "                    dfs((newx, newy), grid, cur + temp)\n",
    "                    grid[newx][newy] = temp\n",
    "\n",
    "        for index, i in enumerate(grid):\n",
    "            for indexj, j in enumerate(i):\n",
    "                if grid[index][indexj]:\n",
    "                    grid[index][indexj] = 0\n",
    "                    dfs((index, indexj), grid, j)\n",
    "                    grid[index][indexj] = j\n",
    "        # dfs(grid)\n",
    "\n",
    "        return(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        dir = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        def dfs(pos, mine, cur):\n",
    "            nonlocal res, grid\n",
    "            res = max(res, cur)\n",
    "            for i in dir:\n",
    "                newx = pos[0] + i[0]\n",
    "                newy = pos[1] + i[1]\n",
    "                if 0 <= newx < len(grid) and 0 <= newy < len(grid[0]) and grid[newx][newy]:\n",
    "                    temp = grid[newx][newy]\n",
    "                    grid[newx][newy] = 0\n",
    "                    dfs((newx, newy), grid, cur + temp)\n",
    "                    grid[newx][newy] = temp\n",
    "\n",
    "        for index, i in enumerate(grid):\n",
    "            for indexj, j in enumerate(i):\n",
    "                if grid[index][indexj]:\n",
    "                    grid[index][indexj] = 0\n",
    "                    dfs((index, indexj), grid, j)\n",
    "                    grid[index][indexj] = j\n",
    "        # dfs(grid)\n",
    "\n",
    "        return(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        def DFS(x,y,visited):\n",
    "            ans = 0\n",
    "            visited.add((x,y))\n",
    "            for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:\n",
    "                tmp_x,tmp_y = x+dx,y+dy\n",
    "                if tmp_x<0 or tmp_x>m-1 or tmp_y<0 or tmp_y>n-1 or (tmp_x,tmp_y) in visited:\n",
    "                    continue\n",
    "                if grid[tmp_x][tmp_y] == 0:\n",
    "                    continue\n",
    "                ans = max(DFS(tmp_x,tmp_y,visited),ans)\n",
    "            visited.remove((x,y))\n",
    "            return ans+grid[x][y]\n",
    "            \n",
    "        res = 0\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    res = max(DFS(i,j,set()),res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        dir = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        def dfs(pos, mine, cur):\n",
    "            nonlocal res, grid\n",
    "            res = max(res, cur)\n",
    "            for i in dir:\n",
    "                newx = pos[0] + i[0]\n",
    "                newy = pos[1] + i[1]\n",
    "                if 0 <= newx < len(grid) and 0 <= newy < len(grid[0]) and grid[newx][newy]:\n",
    "                    temp = grid[newx][newy]\n",
    "                    grid[newx][newy] = 0\n",
    "                    dfs((newx, newy), grid, cur + temp)\n",
    "                    grid[newx][newy] = temp\n",
    "\n",
    "        for index, i in enumerate(grid):\n",
    "            for indexj, j in enumerate(i):\n",
    "                if grid[index][indexj]:\n",
    "                    grid[index][indexj] = 0\n",
    "                    dfs((index, indexj), grid, j)\n",
    "                    grid[index][indexj] = j\n",
    "        # dfs(grid)\n",
    "\n",
    "        return(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        def dfs(x,y):\n",
    "            profit = 0\n",
    "            for nx,ny in ((x+1,y),(x-1,y),(x,y+1),(x,y-1)):\n",
    "                if 0<=nx<m and 0<=ny<n and grid[nx][ny] != 0: #<=0代表走过 或者为0不能走\n",
    "                    tmp = grid[nx][ny]\n",
    "                    grid[nx][ny] = 0\n",
    "                    profit = max(profit,tmp+dfs(nx,ny))\n",
    "                    grid[nx][ny] = tmp\n",
    "            return profit\n",
    "        rs = 0\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] != 0:\n",
    "                    tmp = grid[x][y]\n",
    "                    grid[x][y] = 0\n",
    "                    rs = max(rs,tmp+dfs(x,y))\n",
    "                    grid[x][y] = tmp\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(x: int, y: int, gold: int) -> None:\n",
    "            gold += grid[x][y]\n",
    "            nonlocal ans\n",
    "            ans = max(ans, gold)\n",
    "\n",
    "            rec = grid[x][y]\n",
    "            grid[x][y] = 0\n",
    "\n",
    "            for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:\n",
    "                    dfs(nx, ny, gold)\n",
    "\n",
    "            grid[x][y] = rec\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    dfs(i, j, 0)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(x,y,gold):\n",
    "            nonlocal maxgolden,m,n\n",
    "            rc = grid[x][y]\n",
    "            grid[x][y] = 0\n",
    "            maxgolden = max(maxgolden, rc+gold)\n",
    "            for nx,ny in (x-1,y),(x+1,y),(x,y-1),(x,y+1):\n",
    "                if nx >=0 and nx < m and ny >= 0 and ny < n and grid[nx][ny] > 0:\n",
    "                    dfs(nx,ny,gold+rc)\n",
    "            grid[x][y] = rc\n",
    "\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        maxgolden = 0\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] != 0:\n",
    "                    dfs(x,y,0)\n",
    "        return maxgolden\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(x: int, y: int, gold: int) -> None:\n",
    "            gold += grid[x][y]\n",
    "            nonlocal ans\n",
    "            ans = max(ans, gold)\n",
    "\n",
    "            rec = grid[x][y]\n",
    "            grid[x][y] = 0\n",
    "\n",
    "            for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:\n",
    "                    dfs(nx, ny, gold)\n",
    "\n",
    "            grid[x][y] = rec\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    dfs(i, j, 0)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        def bks(i,j):\n",
    "            if i<0 or j<0 or i>=row or j>=col or grid[i][j]==0: return 0\n",
    "            temp,grid[i][j] = grid[i][j],0\n",
    "            res = max(bks(i+1,j),bks(i,j-1),bks(i,j+1),bks(i-1,j))+temp\n",
    "            grid[i][j]=temp\n",
    "            return res\n",
    "        row,col,ans = len(grid),len(grid[0]),0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j]!=0:\n",
    "                    ans=max(ans,bks(i,j))\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \n",
    "# O()\t\tO()\n",
    "# 最好击败\t%\t\t%\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid) -> int:\n",
    "        def dfs(i, j, total):\n",
    "            t = grid[i][j]\n",
    "            total += t\n",
    "            grid[i][j] = 0  # 标记已走\t越界标记法\n",
    "            # if i - 1 >= 0 and grid[i - 1][j] != 0:  # 向上搜索\n",
    "            #     dfs(i - 1, j, total)\n",
    "            # if i + 1 < m and grid[i + 1][j] != 0:  # 向下搜索\n",
    "            #     dfs(i + 1, j, total)\n",
    "            # if j - 1 >= 0 and grid[i][j - 1] != 0:  # 向左搜索\n",
    "            #     dfs(i, j - 1, total)\n",
    "            # if j + 1 < n and grid[i][j + 1] != 0:  # 向右搜索\n",
    "            #     dfs(i, j + 1, total)\n",
    "            for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:\n",
    "                if 0<=x<m and 0<=y<n and grid[x][y] != 0:\n",
    "                    dfs(x,y,total)\n",
    "\n",
    "            if total > ans[0]:\n",
    "                ans[0] = total\n",
    "            grid[i][j] = t  # 标记回溯\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    dfs(i, j, 0)  # 对每个起点进行深度搜索\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        row,col,ans = len(grid),len(grid[0]),0\n",
    "        def bks(i,j):\n",
    "            if i<0 or j<0 or i>=row or j>=col or grid[i][j]==0: return 0\n",
    "            temp,grid[i][j] = grid[i][j],0\n",
    "            res = max(bks(i+1,j),bks(i,j-1),bks(i,j+1),bks(i-1,j))+temp\n",
    "            grid[i][j]=temp\n",
    "            return res\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j]!=0: ans=max(ans,bks(i,j))\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        row=len(grid)\n",
    "        col=len(grid[0])\n",
    "        ans=0\n",
    "        def dfs(x,y,gold):\n",
    "            nonlocal ans\n",
    "            if gold > ans:\n",
    "                ans=gold\n",
    "            tmp=grid[x][y]\n",
    "            grid[x][y]=0\n",
    "            for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                if 0<=x1<row and 0<=y1<col:\n",
    "                    if  grid[x1][y1]!=0:\n",
    "                        gold=gold+grid[x1][y1]\n",
    "                        dfs(x1,y1,gold)\n",
    "                        gold=gold-grid[x1][y1]\n",
    "            grid[x][y]=tmp\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j]!=0:\n",
    "                    dfs(i,j,grid[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        row,col = len(grid),len(grid[0])\n",
    "        starts = []\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j]!=0:\n",
    "                    starts.append([i,j])\n",
    "        ans = 0\n",
    "        def bks(i,j):\n",
    "            if i<0 or j<0 or i>=row or j>=col or grid[i][j]==0: return 0\n",
    "            temp,grid[i][j] = grid[i][j],0\n",
    "            down = bks(i+1,j)+(grid[i+1][j] if i+1<row else 0)\n",
    "            up = bks(i,j-1)+(grid[i][j-1] if j-1>=0 else 0)\n",
    "            right = bks(i,j+1)+(grid[i][j+1] if j+1<col else 0)\n",
    "            left = bks(i-1,j)+(grid[i-1][j] if i-1>=0 else 0)\n",
    "            res = max(down,up,right,left)\n",
    "            grid[i][j]=temp\n",
    "            return res\n",
    "        for i,j in starts:\n",
    "            ans=max(ans,bks(i,j)+grid[i][j])\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if not (0 <= i < m and 0 <= j < n and grid[i][j]):\n",
    "                return 0\n",
    "            v = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "            ans = max(dfs(i + a, j + b) for a, b in pairwise(dirs)) + v\n",
    "            grid[i][j] = v\n",
    "            return ans\n",
    "            \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        return max(dfs(i, j) for i in range(m) for j in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 因为走的是路径所以一开始的时候感觉应该是使用dfs来解决的\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        # 因为数据范围不是特别大所以考虑使用dfs搜索, 从起点开始搜索\n",
    "        # 表示右左下上\n",
    "        pos = [[0, 1], [0, -1], [-1, 0], [1, 0]]\n",
    "        res = 0\n",
    "        def dfs(x, y, r, c, cur):\n",
    "            nonlocal res\n",
    "            # 一开始递归到这个位置的时候进行更新表示路径能够走到这个位置\n",
    "            res = max(res, cur)\n",
    "            for i in range(4):\n",
    "                # 尝试右左下上四个方向是否可以走下去\n",
    "                curx = x + pos[i][0]\n",
    "                cury = y + pos[i][1]\n",
    "                if 0 <= curx < r and 0 <= cury < c and grid[curx][cury] > 0:\n",
    "                    t = grid[curx][cury]\n",
    "                    grid[curx][cury] = 0\n",
    "                    dfs(curx, cury, r, c, cur + t)\n",
    "                    # 回溯\n",
    "                    grid[curx][cury] = t\n",
    "            return res\n",
    "        \n",
    "        r, c = len(grid), len(grid[0])\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                # 找到起点\n",
    "                if grid[i][j] > 0:\n",
    "                    t = grid[i][j]\n",
    "                    grid[i][j] = 0\n",
    "                    # 最后一个参数表示的是到达当前位置累加的金子\n",
    "                    dfs(i, j, r, c, t)\n",
    "                    grid[i][j] = t\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        def back_track(x, y):\n",
    "            visited.add((x, y))\n",
    "            gold = grid[x][y]\n",
    "            if x + 1 < M and grid[x + 1][y] != 0 and (x + 1, y) not in visited:\n",
    "                gold = max(gold, grid[x][y] + back_track(x + 1, y))\n",
    "            if x - 1 >= 0 and grid[x - 1][y] != 0 and (x - 1, y) not in visited:\n",
    "                gold = max(gold, grid[x][y] + back_track(x - 1, y))\n",
    "            if y + 1 < N and grid[x][y + 1] != 0 and (x, y + 1) not in visited:\n",
    "                gold = max(gold, grid[x][y] + back_track(x, y + 1))\n",
    "            if y - 1 >= 0 and grid[x][y - 1] != 0 and (x, y - 1) not in visited:\n",
    "                gold = max(gold, grid[x][y] + back_track(x, y - 1))\n",
    "            visited.remove((x, y))\n",
    "            return gold\n",
    "\n",
    "        M, N = len(grid), len(grid[0])\n",
    "        visited = set()\n",
    "        no_start = set()\n",
    "        ans = 0\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                if grid[i][j] != 0:\n",
    "                    ans = max(ans, back_track(i, j))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "\n",
    "        def mine(i, j):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n:\n",
    "                return 0\n",
    "            temp = grid[i][j]\n",
    "            if temp == 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            grid[i][j] = 0\n",
    "            for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:\n",
    "                res = max(res, mine(x, y))\n",
    "            grid[i][j] = temp\n",
    "            return res + temp\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    ans = max(ans, mine(i, j))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def mine(i, j):\n",
    "            start = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "\n",
    "            mx = 0\n",
    "            for i2, j2 in (i+1, j), (i-1, j), (i, j+1), (i, j-1):\n",
    "                if -1<i2<m and -1<j2<n and grid[i2][j2]:\n",
    "                    mx = max(mx, mine(i2, j2))\n",
    "                \n",
    "            grid[i][j] = start\n",
    "            return mx + start\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    ans = max(ans, mine(i, j))\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        ma = 0\n",
    "        maxl = []\n",
    "        def DFS(i,j,sums, mlist):\n",
    "            if grid[i][j]==0:\n",
    "                return\n",
    "            nonlocal ma,maxl\n",
    "            sums += grid[i][j]\n",
    "            mlist.append([i,j])\n",
    "            if sums>=ma:\n",
    "                ma = sums\n",
    "                maxl.clear()\n",
    "                maxl = copy.deepcopy(mlist)\n",
    "\n",
    "            for dx,dy in[[-1,0],[1,0],[0,1],[0,-1]]:\n",
    "                nx = i + dx\n",
    "                ny = j + dy\n",
    "                if 0<=nx<len(grid) and 0<=ny<len(grid[0]) and grid[nx][ny]!=0 and [nx,ny] not in mlist:\n",
    "                    DFS(nx,ny,sums,mlist)\n",
    "            mlist.remove([i,j])\n",
    "            return\n",
    "        for x in range(len(grid)):\n",
    "            for y in range(len(grid[0])):\n",
    "                if grid[x][y]!=0:\n",
    "                    DFS(x,y,0,[])\n",
    "\n",
    "        return ma"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        # @cache\n",
    "        def dfs(x, y):\n",
    "            if not (0 <= x < m and 0 <= y < n):\n",
    "                return 0\n",
    "            if vis[x][y] or grid[x][y] == 0:\n",
    "                return 0\n",
    "            vis[x][y] = True\n",
    "            ans = 0 \n",
    "            for nx, ny in (x+1,y),(x-1,y),(x,y+1),(x,y-1):\n",
    "                ans = max(ans, dfs(nx, ny) + grid[x][y])\n",
    "            vis[x][y] = False\n",
    "            return ans\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    ans = max(ans, dfs(i, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        dirs = [(-1,0),(1,0),(0,-1),(0,1)]\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        def dfs(cur, i, j):\n",
    "            nonlocal res\n",
    "            cur = cur + grid[i][j]\n",
    "            res = max(res, cur)\n",
    "\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = i+dx, j+dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and grid[i][j] > 0:\n",
    "                    visited[i][j] = True\n",
    "                    dfs(cur, nx, ny)\n",
    "                    visited[i][j] = False\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    dfs(0, i, j)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(x, y):\n",
    "            if x < 0 or y < 0 or x == m or y == n or not grid[x][y]:\n",
    "                return 0\n",
    "            record = grid[x][y]\n",
    "            grid[x][y] = 0\n",
    "            mx = max(dfs(x + dx, y + dy) for dx, dy in DIRS)\n",
    "            grid[x][y] = record\n",
    "            return record + mx\n",
    "        def helper(x, y):\n",
    "            return sum((nx:=x+dx) < 0 or (ny:=y+dy) < 0 or nx == m or ny == n or not grid[nx][ny] for dx, dy in DIRS) >= 2\n",
    "        return max(dfs(i, j) if grid[i][j] and helper(i, j) else 0 for i in range(m) for j in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "        def dfs(x, y):\n",
    "            max_gold=0\n",
    "            \n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if nx < 0 or nx >= m or ny < 0 or ny >= n or grid[nx][ny] == 0 or (nx, ny) in vis:\n",
    "                    continue\n",
    "                    \n",
    "                vis.add((x, y))\n",
    "                max_gold = max(max_gold, dfs(nx, ny)+ grid[nx][ny])\n",
    "                vis.remove((x,y))\n",
    "            return max_gold \n",
    "\n",
    "        res = 0\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                vis=set()\n",
    "                if grid[i][j] != 0:\n",
    "                    vis.add((i,j))\n",
    "                    res = max(res, dfs(i, j)+grid[i][j])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = 0\n",
    "        def dfs(x,y,cur):\n",
    "            cur += grid[x][y]\n",
    "            nonlocal ans\n",
    "            ans = max(ans,cur)\n",
    "            temp = grid[x][y]\n",
    "            grid[x][y] = 0\n",
    "            for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:\n",
    "                if 0<=x + dx<m and 0<= y + dy<n and grid[x + dx][y + dy]>0:\n",
    "                    dfs(x + dx,y + dy,cur)\n",
    "            grid[x][y] = temp\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    dfs(i,j,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, grid, i, j):\n",
    "        flag = True\n",
    "        if i >= 0 and i < len(grid) and j >= 0 and j < len(grid[0]):\n",
    "            flag = False\n",
    "        if flag:  # 越界\n",
    "            return 0\n",
    "        if grid[i][j] == 0:\n",
    "            return 0\n",
    "        tmp = grid[i][j]\n",
    "        grid[i][j] = 0  # 标记当前位置已走过\n",
    "        up = self.dfs(grid, i - 1, j)\n",
    "        down = self.dfs(grid, i + 1, j)\n",
    "        left = self.dfs(grid, i, j - 1)\n",
    "        right = self.dfs(grid, i, j + 1)\n",
    "        max_route = max(up, down, left, right)\n",
    "        grid[i][j] = tmp  # 位置信息恢复，因为有多条路径会走过当前位置\n",
    "        return grid[i][j] + max_route\n",
    "\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        res = 0  # 最大路径值\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] != 0:  # 遍历所有入口下的路径值\n",
    "                    route_in = self.dfs(grid, i, j)\n",
    "                    res = max(res, route_in)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        gold_num = 0\n",
    "        m,n = len(grid) , len(grid[0])\n",
    "\n",
    "        def dfs(i,j,sum_num):\n",
    "            #对于嵌套函数来说，内部函数可以访问外部函数定义的变量，但是无法修改，若要修改，必须加上nonlocal这个关键字\n",
    "            nonlocal gold_num\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0 :\n",
    "                return \n",
    "            sum_num += grid[i][j]\n",
    "            gold_num = max(gold_num,sum_num)\n",
    "            save = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "            dfs(i - 1,j,sum_num)\n",
    "            dfs(i + 1,j,sum_num)\n",
    "            dfs(i,j - 1,sum_num)\n",
    "            dfs(i,j + 1,sum_num)\n",
    "            grid[i][j] = save\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    dfs(i,j,0)\n",
    "\n",
    "        return gold_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        # def DFS(x,y,visited):\n",
    "        #     ans = 0\n",
    "        #     visited.add((x,y))\n",
    "        #     for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:\n",
    "        #         tmp_x,tmp_y = x+dx,y+dy\n",
    "        #         if tmp_x<0 or tmp_x>m-1 or tmp_y<0 or tmp_y>n-1 or (tmp_x,tmp_y) in visited:\n",
    "        #             continue\n",
    "        #         if grid[tmp_x][tmp_y] == 0:\n",
    "        #             continue\n",
    "        #         ans = max(DFS(tmp_x,tmp_y,visited),ans)\n",
    "        #     visited.remove((x,y))\n",
    "        #     return ans+grid[x][y]\n",
    "            \n",
    "        # res = 0\n",
    "        # m,n = len(grid),len(grid[0])\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         if grid[i][j] != 0:\n",
    "        #             res = max(DFS(i,j,set()),res)\n",
    "        # return res\n",
    "\n",
    "        m, n = len(grid), len(grid[0])  # 取到表的行和列(方便后面多次使用)\n",
    "        ans = 0  # 最终的返回结果\n",
    "\n",
    "        def dfs(x: int, y: int, sum: int):\n",
    "            \"\"\"\n",
    "            这是DFS的递归函数\n",
    "            :param x: 横坐标\n",
    "            :param y: 纵坐标\n",
    "            :param sum: 当前为止的路径和\n",
    "            \"\"\"\n",
    "            sum += grid[x][y]  # 更新路径和\n",
    "            nonlocal ans  # nonlocal声明的是外部嵌套函数内的变量(应该能理解，不能理解的话可以用笨方法把ans也做一个函数参数传进去呗)\n",
    "            ans = max(ans, sum)  # 更新结果\n",
    "            old = grid[x][y]  # 记录一些该位置原来的值，后面要还原回溯哦\n",
    "            grid[x][y] = 0  # 访问过的位置，暂时记为0，不能重复访问(替代了标记集合的作用)\n",
    "            for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):  # 依次遍历相邻的有效位置\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:  # 不越界且非0\n",
    "                    dfs(nx, ny, sum)\n",
    "            grid[x][y] = old  # 还原该位置的值\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:  # 遍历所有可能起点\n",
    "                    dfs(i, j, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        rownum=len(grid)\n",
    "        colnum=len(grid[0])\n",
    "        maxx=0\n",
    "        def check(x,y,num):\n",
    "            nonlocal maxx\n",
    "            temp=grid[x][y]\n",
    "            grid[x][y]=0\n",
    "            direction=[(-1,0),(1,0),(0,1),(0,-1)]\n",
    "            move=False\n",
    "            for i,j in direction:\n",
    "                if 0<=x+i<=rownum-1 and 0<=y+j<=colnum-1 and grid[x+i][y+j]!=0:\n",
    "                    move=True\n",
    "                    check(x+i,y+j,num+temp)\n",
    "            grid[x][y]=temp\n",
    "            if not move:\n",
    "                maxx=max(maxx,num+temp)\n",
    "        \n",
    "        for i in range(rownum):\n",
    "            for j in range(colnum):\n",
    "                if grid[i][j]!=0:\n",
    "                    check(i,j,0)\n",
    "        \n",
    "        return maxx\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        # 返回坐标(x, y)周围最多4个格子中有黄金的格子的数量\n",
    "        def count_around(x, y):\n",
    "            count = 0\n",
    "            if x - 1 >= 0 and grid[x - 1][y] != 0:\n",
    "                count += 1\n",
    "            if x + 1 < len(grid) and grid[x + 1][y] != 0:\n",
    "                count += 1\n",
    "            if y - 1 >= 0 and grid[x][y - 1] != 0:\n",
    "                count += 1\n",
    "            if y + 1 < len(grid[0]) and grid[x][y + 1] != 0:\n",
    "                count += 1\n",
    "            return count\n",
    "\n",
    "        def mine(i, j):\n",
    "            start = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "\n",
    "            mx = 0\n",
    "            for i2, j2 in (i+1, j), (i-1, j), (i, j+1), (i, j-1):\n",
    "                if -1<i2<m and -1<j2<n and grid[i2][j2]:\n",
    "                    mx = max(mx, mine(i2, j2))\n",
    "                \n",
    "            grid[i][j] = start\n",
    "            return mx + start\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] and count_around(i, j) < 3:\n",
    "                    ans = max(ans, mine(i, j))\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        def bks(i,j):\n",
    "            if i<0 or j<0 or i>=row or j>=col or grid[i][j]==0: return 0\n",
    "            temp,grid[i][j] = grid[i][j],0\n",
    "            down = bks(i+1,j)+(grid[i+1][j] if i+1<row else 0)\n",
    "            up = bks(i,j-1)+(grid[i][j-1] if j-1>=0 else 0)\n",
    "            right = bks(i,j+1)+(grid[i][j+1] if j+1<col else 0)\n",
    "            left = bks(i-1,j)+(grid[i-1][j] if i-1>=0 else 0)\n",
    "            res = max(down,up,right,left)\n",
    "            grid[i][j]=temp\n",
    "            return res\n",
    "        row,col,ans = len(grid),len(grid[0]),0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j]!=0:\n",
    "                    ans=max(ans,bks(i,j)+grid[i][j])\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = set()\n",
    "        def dfs(x, y):\n",
    "            cnt = 0\n",
    "            for i, j in [(0,1), (1,0), (-1,0), (0,-1)]:\n",
    "                nx, ny = x+i, y+j\n",
    "                if nx < 0 or ny < 0 or nx >= m or ny >= n or (nx, ny) in visited:\n",
    "                    continue\n",
    "                if grid[nx][ny] == 0:\n",
    "                    continue\n",
    "                visited.add((nx, ny))\n",
    "                cnt = max(cnt, dfs(nx, ny))\n",
    "                visited.remove((nx, ny))\n",
    "            return cnt+grid[x][y]\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                visited.add((i, j))\n",
    "                res = max(res, dfs(i, j))\n",
    "                visited.remove((i, j))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(x: int, y: int, gold: int) -> None:\n",
    "            gold += grid[x][y]\n",
    "            nonlocal ans\n",
    "            ans = max(ans, gold)\n",
    "\n",
    "            rec = grid[x][y]\n",
    "            grid[x][y] = 0\n",
    "\n",
    "            for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:\n",
    "                    dfs(nx, ny, gold)\n",
    "\n",
    "            grid[x][y] = rec\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    dfs(i, j, 0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        def DFS(x,y,visited):\n",
    "            ans = 0\n",
    "            visited.add((x,y))\n",
    "            for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:\n",
    "                tmp_x,tmp_y = x+dx,y+dy\n",
    "                if tmp_x<0 or tmp_x>m-1 or tmp_y<0 or tmp_y>n-1 or (tmp_x,tmp_y) in visited:\n",
    "                    continue\n",
    "                if grid[tmp_x][tmp_y] == 0:\n",
    "                    continue\n",
    "                ans = max(DFS(tmp_x,tmp_y,visited),ans)\n",
    "            visited.remove((x,y))\n",
    "            return ans+grid[x][y]\n",
    "            \n",
    "        res = 0\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    res = max(DFS(i,j,set()),res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        sm = 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def dfs(grid:List[List[int]],i:int,j:int,sumt:int):\n",
    "            nonlocal sm\n",
    "            vis[i][j] = 1\n",
    "            sumt += grid[i][j]\n",
    "            t = 0\n",
    "            for u,v in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):\n",
    "                if 0<=u<len(grid) and 0<=v<len(grid[0]):\n",
    "                    if vis[u][v] == 0 and grid[u][v] != 0:\n",
    "                        dfs(grid,u,v,sumt)\n",
    "                        vis[u][v] = 0\n",
    "                        #sumt -= grid[u][v]\n",
    "                        t += 1\n",
    "            if t == 0:\n",
    "                if sumt > sm:\n",
    "                    sm = sumt\n",
    "\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                vis = [[0]*n for _ in range(m)]\n",
    "                if grid[i][j]  != 0:\n",
    "                    dfs(grid,i,j,0)\n",
    "        return sm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        move = [(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        \n",
    "        def dfs(r,c):\n",
    "            if r < 0 or r >= m or c < 0 or c >= n or not grid[r][c]:\n",
    "                return 0\n",
    "            res = 0\n",
    "            pre = grid[r][c]\n",
    "            grid[r][c] = 0\n",
    "            for x,y in move:\n",
    "                #if (r+x,c+y) in visited:\n",
    "                #    continue\n",
    "                #visited.add((r+x,c+y))\n",
    "                res = max(res,dfs(r+x,c+y)+pre)\n",
    "                #visited.remove((r+x,c+y))\n",
    "            grid[r][c] = pre\n",
    "            return res\n",
    "        ans = 0\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if grid[r][c]:\n",
    "                    ans = max(ans,dfs(r,c))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOVE = ((1, 0), (-1, 0), (0, 1), (0, -1))\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        # 返回坐标(x, y)周围4个格子中有黄金的格子的数量\n",
    "        def count_around(i, j):\n",
    "            count = 0\n",
    "            for di, dj in MOVE:\n",
    "                ni = i + di\n",
    "                nj = j + dj\n",
    "                if -1<ni<m and -1<nj<n and grid[ni][nj]:\n",
    "                    count += 1\n",
    "            return count\n",
    "\n",
    "        def mine(i, j):\n",
    "            start = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "            mx = 0\n",
    "            for di, dj in MOVE:\n",
    "                i2 = i + di\n",
    "                j2 = j + dj\n",
    "                if -1<i2<m and -1<j2<n and grid[i2][j2]:\n",
    "                    temp = mine(i2, j2)\n",
    "                    if temp > mx:\n",
    "                        mx = temp\n",
    "                \n",
    "            grid[i][j] = start\n",
    "            return mx + start\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] and count_around(i, j) < 3:\n",
    "                    temp = mine(i, j)\n",
    "                    if temp > ans:\n",
    "                        ans = temp\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = 0\n",
    "        visited = set()\n",
    "        \n",
    "        def dfs(cur, temp):\n",
    "            nonlocal ans\n",
    "            visited.add(cur)\n",
    "            temp += grid[cur[0]][cur[1]]\n",
    "            ans = max(ans, temp)\n",
    "            for nxt in [(cur[0]-1, cur[1]), (cur[0]+1, cur[1]),(cur[0], cur[1]-1),(cur[0], cur[1]+1)]:\n",
    "                if 0 <= nxt[0] < m and 0 <= nxt[1] < n and nxt not in visited and grid[nxt[0]][nxt[1]] > 0:\n",
    "                    dfs(nxt, temp)\n",
    "            visited.remove(cur)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dfs((i, j), 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        def DFS(x,y,visited):\n",
    "            ans = 0\n",
    "            visited.add((x,y))\n",
    "            for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:\n",
    "                tmp_x,tmp_y = x+dx,y+dy\n",
    "                if tmp_x<0 or tmp_x>m-1 or tmp_y<0 or tmp_y>n-1 or (tmp_x,tmp_y) in visited:\n",
    "                    continue\n",
    "                if grid[tmp_x][tmp_y] == 0:\n",
    "                    continue\n",
    "                ans = max(DFS(tmp_x,tmp_y,visited),ans)\n",
    "            visited.remove((x,y))\n",
    "            return ans+grid[x][y]\n",
    "            \n",
    "        res = 0\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    res = max(DFS(i,j,set()),res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        def dfs(i, j):\n",
    "            old = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "            cnt = 0\n",
    "            for x, y in (i+1, j), (i-1, j), (i, j+1),(i, j-1):\n",
    "                if 0 <=x < m and 0 <= y < n and grid[x][y]:\n",
    "                    cnt = max(cnt, dfs(x, y))\n",
    "            grid[i][j] = old\n",
    "            return cnt + old\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    res = max(res, dfs(i,j))\n",
    "        return res     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    res = 0\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def go(x, y):\n",
    "            if x < 0 or x >= m:\n",
    "                return 0\n",
    "            if y < 0 or y >= n:\n",
    "                return 0\n",
    "            if grid[x][y] == 0:\n",
    "                return 0\n",
    "            cur = grid[x][y]\n",
    "            grid[x][y] = 0\n",
    "            res = 0\n",
    "            res = max(res, cur + go(x + 1, y))\n",
    "            res = max(res, cur + go(x - 1, y))\n",
    "            res = max(res, cur + go(x, y + 1))\n",
    "            res = max(res, cur + go(x, y - 1))\n",
    "            grid[x][y] = cur\n",
    "            return res\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    self.res = max(go(i,j), self.res)\n",
    "        return self.res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        self.res = 0\n",
    "        def helpdef(i,j,k):\n",
    "            if grid[i][j] == 0:\n",
    "                return\n",
    "\n",
    "            k += grid[i][j]\n",
    "\n",
    "            self.res = max(k, self.res)\n",
    "            temp = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "            if 0 < i <= len(grid) - 1:\n",
    "                helpdef(i - 1, j, k)\n",
    "            if 0 <= i < len(grid) - 1:\n",
    "                helpdef(i + 1, j, k)\n",
    "            if 0 < j <= len(grid[0]) - 1:\n",
    "                helpdef(i, j - 1, k)\n",
    "            if 0 <= j < len(grid[0]) - 1:\n",
    "                helpdef(i, j + 1, k)\n",
    "            grid[i][j] = temp\n",
    "\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                helpdef(i, j, 0)\n",
    "\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def getMaximumGold(self, grid):\n",
    "       \n",
    "        dx = [1, -1, 0, 0]\n",
    "        dy = [0, 0, 1, -1]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = set()\n",
    "        self.res = 0\n",
    "        \n",
    "        def dfs(x0, y0, tmp):\n",
    "            self.res = max(self.res, tmp)\n",
    "            for k in range(4):\n",
    "                x = x0 + dx[k]\n",
    "                y = y0 + dy[k]\n",
    "                \n",
    "                if 0 <= x < m and 0 <= y < n and (x, y) not in visited and grid[x][y] != 0:\n",
    "                    visited.add((x, y))\n",
    "                    dfs(x, y, tmp + grid[x][y])\n",
    "                    visited.remove((x, y))\n",
    "                    \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                visited.add((i, j))\n",
    "                dfs(i, j, grid[i][j])\n",
    "                visited.remove((i, j))\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        v=set()\n",
    "        def g(i,j):\n",
    "            res =0\n",
    "            for a,b in [[1,0],[-1,0],[0,1],[0,-1]]:\n",
    "                x=i+a\n",
    "                y=j+b\n",
    "                if 0<=x<n and 0<=y<m and grid[x][y]!=0 and (x,y) not in v:\n",
    "                    v.add((x,y))\n",
    "                    res=max(res,g(x,y))\n",
    "                    v.remove((x,y))\n",
    "            return res+grid[i][j]\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                v=set()\n",
    "\n",
    "                if grid[i][j]!=0:\n",
    "                    v.add((i,j))    \n",
    "                    ans=max(g(i,j),ans)\n",
    "        return ans                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        def DFS(x,y,visited):\n",
    "            ans = 0\n",
    "            visited.add((x,y))\n",
    "            for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:\n",
    "                tmp_x,tmp_y = x+dx,y+dy\n",
    "                if tmp_x<0 or tmp_x>m-1 or tmp_y<0 or tmp_y>n-1 or (tmp_x,tmp_y) in visited:\n",
    "                    continue\n",
    "                if grid[tmp_x][tmp_y] == 0:\n",
    "                    continue\n",
    "                ans = max(DFS(tmp_x,tmp_y,visited),ans)\n",
    "            visited.remove((x,y))\n",
    "            return ans+grid[x][y]\n",
    "            \n",
    "        res = 0\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    res = max(DFS(i,j,set()),res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        visited = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]\n",
    "        def dfs(i, j, v):\n",
    "            visited[i][j] = 1\n",
    "            nonlocal ans\n",
    "            v += grid[i][j]\n",
    "            ans = max(ans, v)\n",
    "            directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "            for k in directions:\n",
    "                new_i = i + k[0]\n",
    "                new_j = j + k[1]\n",
    "                if 0 <= new_i < len(grid) and 0 <= new_j < len(grid[0]) and grid[new_i][new_j] != 0 and visited[new_i][new_j] == 0:\n",
    "                    dfs(new_i, new_j, v)\n",
    "            visited[i][j] = 0\n",
    "            v -= grid[i][j]\n",
    "        for x in range(len(grid)):\n",
    "            for y in range(len(grid[0])):\n",
    "                if grid[x][y] != 0:\n",
    "                    dfs(x, y, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(x: int, y: int, gold: int) -> None:\n",
    "            nonlocal ans\n",
    "            gold += grid[x][y]\n",
    "            ans = max(ans, gold)\n",
    "            rec = grid[x][y]\n",
    "            grid[x][y] = 0\n",
    "\n",
    "            for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:\n",
    "                    dfs(nx, ny, gold)\n",
    "\n",
    "            grid[x][y] = rec\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    dfs(i, j, 0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [ [False for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        pos = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        ans = 0\n",
    "        cur_sum = 0\n",
    "        def dfs(i: int, j: int) -> None:\n",
    "            nonlocal cur_sum, ans\n",
    "            visited[i][j] = True \n",
    "\n",
    "            cur_sum += grid[i][j]\n",
    "            ans = max(ans, cur_sum)\n",
    "\n",
    "            for dx, dy in pos:\n",
    "                nxt_i, nxt_j = i + dx, j + dy \n",
    "                if 0 <= nxt_i < m and 0 <= nxt_j < n and not visited[nxt_i][nxt_j] and grid[nxt_i][nxt_j] != 0:\n",
    "                    # cur_sum += grid[nxt_i][nxt_j]\n",
    "                    \n",
    "                    dfs(nxt_i, nxt_j)\n",
    "                    # cur_sum -= grid[nxt_i][nxt_j]\n",
    "            cur_sum -= grid[i][j]\n",
    "            visited[i][j] = False\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                \n",
    "                if grid[i][j] != 0 and not visited[i][j]:\n",
    "                    cur_sum = 0\n",
    "                    dfs(i, j)\n",
    "        \n",
    "        return ans \n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        def dfs(i, j, gold):\n",
    "            gold += grid[i][j]\n",
    "            nonlocal ans\n",
    "            ans = max(ans, gold)\n",
    "            rec = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "            for nx, ny in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:\n",
    "                    dfs(nx, ny, gold)\n",
    "            grid[i][j] = rec\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    dfs(i, j, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        ans = 0\n",
    "        def dfs(i,j,s):\n",
    "            s+= grid[i][j]\n",
    "            nonlocal ans\n",
    "            if s > ans:\n",
    "                ans =s\n",
    "            tmp =grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "            for x,y in (i-1,j),(i+1,j),(i,j-1),(i,j+1):\n",
    "                if 0<=x<m and 0<=y<n and grid[x][y]:\n",
    "                    dfs(x,y,s)\n",
    "            grid[i][j] =tmp \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    dfs(i,j,0)\n",
    "        return ans\n",
    "                    \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        ans=0\n",
    "        def dfs(x,y,sum):\n",
    "            sum+=grid[x][y]\n",
    "            nonlocal ans\n",
    "            ans=max(ans,sum)\n",
    "            s=grid[x][y]\n",
    "            f=grid[x][y]\n",
    "            grid[x][y]=0\n",
    "            for nx,ny in ((x-1,y),(x+1,y),(x,y-1),(x,y+1)):\n",
    "                if 0<=nx<m and 0<=ny<n and grid[nx][ny]>0:\n",
    "                    dfs(nx,ny,sum)\n",
    "            grid[x][y]=f\n",
    "            return ans\n",
    "    \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]!=0:\n",
    "                    dfs(i,j,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        def dfs(x, y, res):\n",
    "            nonlocal ans\n",
    "            vis[x][y] = True\n",
    "            res += grid[x][y]\n",
    "            ans = max(ans, res)\n",
    "            for dx, dy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n",
    "                if 0 <= dx < m and 0 <= dy < n and not vis[dx][dy] and grid[dx][dy] > 0:\n",
    "                    dfs(dx, dy, res)\n",
    "            vis[x][y] = False\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    dfs(i, j, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if not (0 <= i < m and 0 <= j < n and grid[i][j]):\n",
    "                return 0\n",
    "            v = grid[i][j]\n",
    "            grid[i][j] = 0\n",
    "            ans = max(dfs(i + a, j + b) for a, b in pairwise(dirs)) + v\n",
    "            grid[i][j] = v\n",
    "            return ans\n",
    "            \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        return max(dfs(i, j) for i in range(m) for j in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        def insideGrid(i,j):\n",
    "            return 0 <= i < rows and 0 <= j < cols\n",
    "\n",
    "        def dfs(i,j,amount):\n",
    "            nonlocal ans\n",
    "            ans = max(ans, amount)\n",
    "            for d in directions:\n",
    "                ni, nj = i+d[0], j+d[1]\n",
    "                if insideGrid(ni,nj) and grid[ni][nj] != 0 and not visited[ni][nj]:\n",
    "                    visited[ni][nj] = 1\n",
    "                    dfs(ni,nj,amount+grid[ni][nj])\n",
    "                    visited[ni][nj] = 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        rows = len(grid)\n",
    "        cols = len(grid[0])\n",
    "        ans = 0\n",
    "        directions = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "        visited = [[0] * cols for _ in range(rows)]\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if grid[i][j] != 0:\n",
    "                    # print(\"start: \", (i,j))\n",
    "                    visited[i][j] = 1\n",
    "                    dfs(i,j,grid[i][j])\n",
    "                    visited[i][j] = 0\n",
    "                    # print(\"ans: \", ans)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        used = [[False] * m for _ in range(n)]\n",
    "        def dfs(r, c):\n",
    "            nonlocal ans, cur\n",
    "            if (r < 0 or r >= n or\n",
    "                c < 0 or c >= m or\n",
    "                grid[r][c] <= 0 or\n",
    "                used[r][c]):\n",
    "                return\n",
    "            \n",
    "            used[r][c] = True\n",
    "            cur += grid[r][c]\n",
    "            if cur > ans:\n",
    "                ans = cur\n",
    "            dfs(r - 1, c)\n",
    "            dfs(r + 1, c)\n",
    "            dfs(r, c - 1)\n",
    "            dfs(r, c + 1)\n",
    "            cur -= grid[r][c]\n",
    "            used[r][c] = False\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    cur = 0\n",
    "                    dfs(i, j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        def DFS(x,y,visited):\n",
    "            ans = 0\n",
    "            visited.add((x,y))\n",
    "            for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:\n",
    "                tmp_x,tmp_y = x+dx,y+dy\n",
    "                if tmp_x<0 or tmp_x>m-1 or tmp_y<0 or tmp_y>n-1 or (tmp_x,tmp_y) in visited:\n",
    "                    continue\n",
    "                if grid[tmp_x][tmp_y] == 0:\n",
    "                    continue\n",
    "                ans = max(DFS(tmp_x,tmp_y,visited),ans)\n",
    "            visited.remove((x,y))\n",
    "            return ans+grid[x][y]\n",
    "            \n",
    "        res = 0\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 0:\n",
    "                    res = max(DFS(i,j,set()),res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumGold(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        b = set()\n",
    "        g_x, g_y = len(grid[0]), len(grid)\n",
    "\n",
    "        def backtrack(x, y, count, vis_local):\n",
    "            nonlocal res\n",
    "            if count > res:\n",
    "                res = count\n",
    "            for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                n_x, n_y = x + i, y + j\n",
    "                if 0 <= n_x < g_x and 0 <= n_y < g_y and vis_local[n_y][n_x] and grid[n_y][n_x]:\n",
    "                    vis_local[n_y][n_x] = 0\n",
    "                    backtrack(n_x, n_y, count + grid[n_y][n_x], vis_local)\n",
    "                    vis_local[n_y][n_x] = 1\n",
    "\n",
    "        def find_corner(i, j):\n",
    "            count = 0\n",
    "            for x, y in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                n_x, n_y = x + i, y + j\n",
    "                if 0 <= n_x < g_x and 0 <= n_y < g_y and grid[n_y][n_x]:\n",
    "                    count += 1\n",
    "            return count <= 2\n",
    "\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] and find_corner(j, i):\n",
    "                    print(i, j)\n",
    "                    vis_local = [[1] * g_x for _ in range(g_y)]\n",
    "                    vis_local[i][j] = 0\n",
    "                    backtrack(j, i, grid[i][j], vis_local)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
